%0 Conference Proceedings
%4 sid.inpe.br/sibgrapi/2011/07.07.18.15
%2 sid.inpe.br/sibgrapi/2011/07.07.18.15.05
%@doi 10.1109/SIBGRAPI.2011.24
%T Memory-Efficient Computation of Persistent Homology for 3D Images using Discrete Morse Theory
%D 2011
%A Günther, David,
%A Reininghaus, Jan,
%A Wagner, Hubert,
%A Hotz, Ingrid,
%@affiliation Zuse Institute Berlin
%@affiliation Zuse Institute Berlin
%@affiliation Institute of Computer Science, Jagiellonian University
%@affiliation Zuse Institute Berlin
%E Lewiner, Thomas,
%E Torres, Ricardo,
%B Conference on Graphics, Patterns and Images, 24 (SIBGRAPI)
%C Maceió, AL, Brazil
%8 28-31 Aug. 2011
%I IEEE Computer Society
%J Los Alamitos
%S Proceedings
%K persistent homology, Morse-Smale complex, discrete Morse theory, large data.
%X We propose a memory-efficient method that com- putes persistent homology for 3D gray-scale images. The basic idea is to compute the persistence of the induced Morse-Smale complex. Since in practice this complex is much smaller than the input data, significantly less memory is required for the subsequent computations. We propose a novel algorithm that efficiently extracts the Morse-Smale complex based on algorithms from discrete Morse theory. The proposed algorithm is thereby optimal with a computational complexity of O(n2). The per- sistence is then computed using the Morse-Smale complex by applying an existing algorithm with a good practical running time. We demonstrate that our method allows for the computation of persistent homology for large data on commodity hardware.
%@language en
%3 persistenceLargeData.pdf